define("dojox/treemap/_utils", ["dojo/_base/array"], function (arr) {
    var utils = {
        group:function (/*Array*/items, /*Array*/groupingFunctions, /*Function*/measureFunction) {
            var response = {
                children:[]
            };
            var merge = function (obj, entry) {
                if (!obj.__treeValue) {
                    obj.__treeValue = 0;
                }
                obj.__treeValue += measureFunction(entry);
                return obj;
            };
            // we go over each entry in the array
            arr.forEach(items, function (entry) {
                var r = response;
                // for this entry, for each rowField we
                // look at the actual value for this rowField
                // and create a holding object for this
                // value in response if it does not exist
                arr.forEach(groupingFunctions, function (groupingFunction, j) {
                    // actual value for the rowField
                    var data = groupingFunction(entry);
                    // create child if undefined
                    var child = utils.find(r.children, function (item) {
                        return (item.__treeName == data);
                    });
                    if (!child) {
                        r.children.push(child = {
                            __treeName:data,
                            __treeID:data + Math.random(),
                            children:[]
                        });
                    }
                    child = merge(child, entry);
                    if (j != groupingFunctions.length - 1) {
                        // branch & prepare response for
                        // next call
                        r = child;
                    } else {
                        // add the entry to the leaf!
                        child.children.push(entry);
                    }
                });
                r = merge(r, entry);
            });
            return response;
        },
        find:function (/*Array*/array, /*Function*/callback) {
            var l = array.length;
            for (var i = 0; i < l; ++i) {
                if (callback.call(null, array[i])) {
                    return array[i];
                }
            }
            return null;
        },
        solve:function (items, width, height, areaFunc, rtl) {
            //
            // Create temporary TreeMap elements
            //
            var treeMapElements = utils.initElements(items, areaFunc);
            var dataTotal = treeMapElements.total;
            var elements = treeMapElements.elements;

            var realSize = dataTotal;

            if (dataTotal == 0) {
                if (elements.length == 0) {
                    return {
                        items:items, rects:[], total:0
                    };
                }
                arr.forEach(elements, function (element) {
                    element.size = element.sizeTmp = 100;
                });
                dataTotal = elements.length * 100;
            }

            //
            // 	Sort the TreeMap elements
            //
            elements.sort(function (b, a) {
                return a.size - b.size;
            });

            utils._compute(width, height, elements, dataTotal);

            //
            // Restore initial Sort order
            //
            elements.sort(function (a, b) {
                return a.index - b.index;
            });

            var result = {};
            result.elements = elements;
            result.size = realSize;

            rects = arr.map(elements, function (element) {
                return {
                    x:rtl ? width - element.x - element.width : element.x, y:element.y, w:element.width, h:element.height
                };
            });

            result.rectangles = rects;

            return result;
        },
        initElements:function (items, areaFunc) {
            var total = 0;
            var elements = arr.map(items, function (item, index) {
                var size = areaFunc != null ? areaFunc(item) : 0;
                if (size < 0) {
                    throw new Error("item size dimension must be positive");
                }
                total += size;
                return {
                    index:index, size:size, sizeTmp:size
                };
            });
            return {
                elements:elements, total:total
            };
        },
        _compute:function (width, height, elements, total) {
            var valueScale = ((width * height) / total) / 100;

            arr.forEach(elements, function (element) {
                element.sizeTmp *= valueScale;
            });

            var start = 0;
            var end = 0;
            var aspectCurr = -1 >>> 1; // int.MaxValue;
            var aspectLast;
            var offsetX = 0;
            var offsetY = 0;
            var tmp_width = width;
            var tmp_height = height;

            var vert = tmp_width > tmp_height;

            while (end != elements.length) {
                aspectLast = utils._trySolution(elements, start, end, vert, tmp_width, tmp_height);

                if ((aspectLast > aspectCurr) || (aspectLast < 1)) {
                    var currX = 0;
                    var currY = 0;

                    for (var n = start; n < end; n++) {
                        elements[n].x = offsetX + currX;
                        elements[n].y = offsetY + currY;
                        if (vert) {
                            currY += elements[n].height;
                        } else {
                            currX += elements[n].width;
                        }
                    }

                    if (vert) {
                        offsetX += elements[start].width;
                    } else {
                        offsetY += elements[start].height;
                    }

                    tmp_width = width - offsetX;
                    tmp_height = height - offsetY;

                    vert = tmp_width > tmp_height;

                    start = end;
                    end = start;

                    aspectCurr = -1 >>> 1; // int.MaxValue;
                    continue;
                } else {
                    for (var n = start; n <= end; n++) {
                        elements[n].width = elements[n].widthTmp;
                        elements[n].height = elements[n].heightTmp;
                    }
                    aspectCurr = aspectLast;
                }
                end++;
            }

            var currX1 = 0;
            var currY1 = 0;

            for (var n = start; n < end; n++) {
                elements[n].x = offsetX + currX1;
                elements[n].y = offsetY + currY1;
                if (vert) {
                    currY1 += elements[n].height;
                } else {
                    currX1 += elements[n].width;
                }
            }

        },
        _trySolution:function (elements, start, end, vert, tmp_width, tmp_height) {
            var total = 0;
            var aspect = 0;
            var localWidth = 0;
            var localHeight = 0;

            for (var n = start; n <= end; n++) {
                total += elements[n].sizeTmp;
            }

            if (vert) {
                if (tmp_height == 0) {
                    localWidth = localHeight = 0;
                } else {
                    localWidth = total / tmp_height * 100;
                    localHeight = tmp_height;
                }
            } else {
                if (tmp_width == 0) {
                    localWidth = localHeight = 0;
                } else {
                    localHeight = total / tmp_width * 100;
                    localWidth = tmp_width;
                }
            }

            for (var n = start; n <= end; n++) {
                if (vert) {
                    elements[n].widthTmp = localWidth;
                    if (total == 0) {
                        elements[n].heightTmp = 0;
                    } else {
                        elements[n].heightTmp = localHeight * elements[n].sizeTmp / total;
                    }
                } else {
                    if (total == 0) {
                        elements[n].widthTmp = 0;
                    } else {
                        elements[n].widthTmp = localWidth * elements[n].sizeTmp / total;
                    }
                    elements[n].heightTmp = localHeight;
                }
            }
            aspect = Math.max(elements[end].heightTmp / elements[end].widthTmp, elements[end].widthTmp
                / elements[end].heightTmp);
            if (aspect == undefined) {
                return 1;
            }
            return aspect;
        }
    };
    return utils;
});
